package alo.p12.work;

import org.junit.Test;

import java.util.Arrays;
import java.util.Random;

/**
 * @ClassName FindMedian
 * @Description 查找两个数组总体的中位数
 * @Author Fanxc
 * @DATE 2021/3/14 11:58
 * @Version 1.0
 */
public class FindMedian {
    int aMed,bMed;
    int findMedian(int[] A,int alo,int ahi,int[] B,int blo,int bhi){
        int aMid=alo+(ahi-alo)/2;
        aMed=A[aMid];
        int bMid=blo+(bhi-blo)/2;
        bMed=B[bMid];
        if (aMed==bMed){
            return aMed;
        }
        if (ahi-alo+bhi-blo<=4){
            return (aMed+bMed)/2;
        }else if (aMed<bMed){
            findMedian(A,aMid+1,ahi,B,blo,bMid-1);
        }else {
            findMedian(A,alo,aMid-1,B,bMid+1,bhi);
        }
        return (aMed+bMed)/2;
    }

    @Test
    public void test(){
        int[] a=new int[11];
        int[] b=new int[11];
        int[] c=new int[22];
        Random random=new Random();
        for(int i=0;i<a.length;i++)
            c[i]=a[i]=random.nextInt(101);  //随机生成10个0到100的数字
        Arrays.sort(a);
        System.out.println("生成的结果是："+ Arrays.toString(a));
        for(int i=0;i<b.length;i++)
            c[i+a.length]=b[i]=random.nextInt(101);  //随机生成10个0到100的数字
        Arrays.sort(b);
        System.out.println("生成的结果是："+ Arrays.toString(b));
        Arrays.sort(c);
        System.out.println("生成的结果是："+ Arrays.toString(c));
        System.out.println("中位数是："+(c[10]+c[11])/2);
        int secondMax = findMedian(a,0,10,b,0,10);
        System.out.println("中位数是："+secondMax);
    }

    class Solution {
        public double findMedianSortedArrays(int[] nums1, int[] nums2) {
            int n1 = nums1.length;
            int n2 = nums2.length;
            if (n1>n2)
                return findMedianSortedArrays(nums2, nums1);
            int k = (n1 + n2 + 1)/2;
            int left = 0;
            int right = n1;
            while(left < right){
                int m1 = left +(right - left)/2;
                int m2 = k - m1;
                if (nums1[m1] < nums2[m2-1])
                    left = m1 + 1;
                else
                    right = m1;
            }
            int m1 = left;
            int m2 = k - left;
            int c1 = Math.max(m1 <= 0 ? Integer.MIN_VALUE : nums1[m1-1],
                    m2 <= 0 ? Integer.MIN_VALUE : nums2[m2-1]);
            if ((n1 + n2) % 2 == 1)
                return c1;
            int c2 = Math.min( m1 >= n1 ? Integer.MAX_VALUE :nums1[m1],
                    m2 >= n2 ? Integer.MAX_VALUE : nums2[m2]);
            return (c1 + c2) * 0.5;

        }
    }
}
